<?php

/*
	Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level.

	Solution 1: Obviously the first choice is a Breadth First Search. How to determine "end of leve"? Use a second stack... Or use a counter
	Solution 2: Breadth First Search is not allowed. We can only use DFS
*/

require_once 'util.php';

importJS();

$arr = generateRandomArray(0, 99, 10);

$bt = null;
foreach( $arr as $value ){
	$bt = bt_insert($value, $bt);
}

bt_draw( $bt );

echo "BFS:<br/>";
bt_level_order_bfs( $bt );

echo "<br/>";

echo "DFS:<br/>";
bt_level_order_dfs( $bt );

function bt_level_order_bfs( $root ){
	if( !$root ){
		return;
	}

	// 1. 2 stacks
	/*
	$display = array();
	$queue = array();

	array_unshift( $display, $root );
	
	while( count( $display) ){
		$cur = array_pop( $display );
		echo "{$cur->value} ";

		if( $cur->left ){
			array_unshift( $queue, $cur->left );
		}
		if( $cur->right ){
			array_unshift( $queue, $cur->right );	
		}

		// Finishing this level, swap the two stacks
		if( !count($display) ){
			// Swap
			$temp = $queue;
			$queue = $display;
			$display = $temp;

			echo "<br/>";
		}

	}*/

	// 2. 1 stack + counters
	$queue = array();
	$currentLevel = 0;
	$nextLevel = 0;

	array_unshift( $queue, $root );
	$currentLevel++;
	
	while( count( $queue) ){
		$cur = array_pop( $queue );
		$currentLevel--;
		echo "{$cur->value} ";

		if( $cur->left ){
			array_unshift( $queue, $cur->left );
			$nextLevel++;
		}
		if( $cur->right ){
			array_unshift( $queue, $cur->right );	
			$nextLevel++;
		}

		if( 0 >= $currentLevel ){
			// Hooray!
			$currentLevel = $nextLevel;
			$nextLevel = 0;
			echo "<br/>";
		}
	}
}

// Strange solution...
function bt_level_order_dfs( $root ){
	$level = 1;
	while( bt_print_level( $root, $level ) ){
		echo "<br/>";
		$level++;
	}
}

// This print level will return the total nodes printed
// When returning 0 means passed the max height, we break the loop
function bt_print_level( $root, $level ){
	if( !$root || $level <= 0 ){
		return 0;
	}

	$level--;
	$result = 0;
	if( 0 == $level ){
		echo "{$root->value} ";
		$result = 1;
	}
	else {
		$result += bt_print_level( $root->left, $level );
		$result += bt_print_level( $root->right, $level );	
	}

	return $result;
}